package leetcodev1.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode40 {
    private List<List<Integer>> ret = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, new ArrayList<>());
        return this.ret;
    }

    //不选 1 7 过滤掉
    //1 不选 7
    private void dfs(int[] candidates, int target, int index, ArrayList<Integer> route) {
        if (target == 0) {
            this.ret.add(new ArrayList<>(route));
            return;
        }

        if (index >= candidates.length) {
            return;
        }

        //如果不选当前值就都不选
        int nextIndex = index;
        while (nextIndex < candidates.length && candidates[nextIndex] == candidates[index]) {
            nextIndex++;
        }
        dfs(candidates, target, nextIndex, route);

        if (target - candidates[index] >= 0) {
            route.add(candidates[index]);
            dfs(candidates, target - candidates[index], index + 1, route);
            route.remove(route.size() - 1);
        }
    }
}
